#include <cstdio>
#include <memory.h>

int max( int a, int b ) { return ( a < b )?b :a; }

int f[ 801 ], g[ 801 ], n, m;
int x, y, a[ 801 ], b[ 801 ], p[ 801 ], q[ 801 ];

void init( )
{
    int i, j;
    scanf("%d", &x);
    for ( i = 0; i < x; i++ )
        scanf("%d%d", &a[ i ], &p[ i ]);
    scanf("%d", &y);
    for ( i = 0; i < y; i++ )
        scanf("%d%d", &b[ i ], &q[ i ]);
    for ( i = 0; i <= m; i++ )
        f[ i ] = -1000000000;
    for ( i = 0; i < x; i++ )
        for ( j = 0; j < y; j++ )
            if ( a[ i ] + b[ j ] <= m && a[ i ] != -1000000000 && b[ j ] != -1000000000 )
                f[ a[ i ] + b[ j ] ] = max( f[ a[ i ] + b[ j ] ], p[ i ] + q[ j ] );
    for ( i = 1; i <= m; i++ )
        f[ i ] = max( f[ i ], f[ i - 1 ] );
}

void work( )
{
    int p = 1, i, j, g2[ 801 ];
    while ( p <= n ) p <<= 1;
    p >>= 2;
    for ( i = 0; i <= m; i++ )
        g[ i ] = f[ i ];
    while ( p )
    {
        for ( i = 0; i <= m; i++ ) g2[ i ] = -1000000000;
        for ( i = m; i >= 0; i-- )
            for ( j = 0; j <= i; j++ )
                if ( g[ i - j ] != -1000000000 && g[ j ] != -1000000000 )
                    g2[ i ] = max( g2[ i ], g[ i - j ] + g[ j ] );
        for ( i = 1; i <= m; i++ )
            g2[ i ] = max( g2[ i ], g2[ i - 1 ] );
        for ( i = 0; i <= m; i++ )
        {
            g[ i ] = g2[ i ];
            g2[ i ] = -1000000000;
        }
        if ( p & n )
        {
            for ( i = m; i >= 0; i-- )
                for ( j = 0; j <= i; j++ )
                    if ( g[ i - j ] != -1000000000 && f[ j ] != -1000000000 )
                        g2[ i ] = max( g2[ i ], g[ i - j ] + f[ j ] );
            for ( i = 1; i <= m; i++ )
                g2[ i ] = max( g2[ i ], g2[ i - 1 ] );
            for ( i = 0; i <= m; i++ ) g[ i ] = g2[ i ];
        }
        p >>= 1;
    }
    printf("%d\n", g[ m ]);
}

int main( )
{
    while ( scanf("%d%d", &n, &m) )
    {
        if ( n == 0 && m == 0 )
            break;
        init( );
        work( );
    }
    return 0;
}
